package com.scott.ch050;

import java.util.Arrays;

/**
 * @author 黄后林
 * @version 1.0
 * @note  归并排序
 * @date 2022-03-12 22:11:55
 */
public class Merge {

    // 归并所需要的辅助数组
    private static Comparable[] assist;

    private static  int couter=1;
    private static  int group=1;


    // 比较before元素是否小于after元素
    private static boolean less(Comparable before,Comparable after){
        return before.compareTo(after)<0;
    }

    // 把数组下标为i和下标为j的元素交换位置
    private static void exchage(Comparable[] a, int i, int j){
        Comparable t = a[i];
        a[i]=a[j];
        a[j]=t;
    }

    // 对数组array进行归并排序
    public  static void sort(Comparable[] array){

        //1、初始化辅助数组assist   辅助数组的大小和待排序的数组的大小相等
        assist = new Comparable[array.length];

        //2、定义2个变量low和high [ low=待排序的数组的最小的索引 high=待排序的数组的最大的索引 ]
        int low =0;
        int high= array.length-1;

        //3、调用sort的重载方法完成所有元素的排序
        sort(array,low,high);

    }

    private static  void print(Comparable[] array,int low,int high){

        System.out.print("{");
        for(int index = low; index<=high;index++){
            System.out.print(array[index] +" ");
        }
        System.out.println("}");
    }

    // 对数组array中下标从low到high的元素进行排序
    // low <= index <= high
    private  static void sort(Comparable[] array,int low,int high){

        System.out.println("第"+ group++ + "次分组...");

        //1、做安全性的校验 lo<hi
        if(high <= low){
            System.out.println("high=low="+high +" 不排序");
            return;
        }

        // 对于数组 {8、4、5、7、 1、3、6、2}
        // 可知：low=0 high=7

        // 可以求出   mid= 0+(7-0)/2=0+3=3
        // 下标[0,3]一组、 下标[4,7]一组

        // 第1组:     low<=index<=mid     [ 左子组 ] = [ 左小组 ]
        // 第2组:     mid+1<=index<=high  [ 右子组 ] = [ 右小组 ]
        int mid = low+(high-low)/2;

        //3、分别对这2组数据进行排序
        print(array,low,mid);
        sort(array,low,mid);

        print(array,mid+1,high);
        sort(array,mid+1,high);

        //4、合并2小组为1大组
        merge(array,low,mid,high);



    }

    // 然后把2个小组合并成1个大组
    // 第1组:     lo<=index<=mid
    // 第2组:     mid+1<=index<=hi
    // 比如把【4、8】和【5、7】合并成 【4、5、7、8】
    private  static void merge(Comparable[] array,int low,int mid , int high){

        System.out.println("第=" + (couter++) + "次排序" );
        System.out.println("lo=" + low +  "\thigh=" + high +"\tmid=" + mid   );

        //1、定义3个指针p1、p2、i
        int p1=low;
        int p2=mid+1;
        int i=low;

        //2、找出p1和p2指向元素中 最小的元素  然后把最小的元素复制到辅助数组的i处 然后p1或p2指针右移1位
        while(p1<=mid && p2<=high){

            if(less(array[p1],array[p2])){
                //如果p1指向的元素比p2指向的元素小 就把p1指向的元素复制到辅助数组中
                assist[i++]=array[p1++];
            }else{
                //如果p2指向的元素比p1指向的元素小 就把p1指向的元素复制到辅助数组中
                assist[i++]=array[p2++];
            }

        }
        //3、如果p1已经移动到自己可以达到的最大处 直接把p2指向的值复制到辅助数组的i处 反之也是

        //-----------------------------这2个while循环实际只会走1个----------------------------- BEGIN
        while(p2<=high){
            assist[i++]=array[p2++];

        }
        while(p1<=mid){
            assist[i++]=array[p1++];
        }
        //-----------------------------这2个while循环实际只会走1个----------------------------- END

        //上面3个循环走完后、就已经把左子组合右子组中的所有数据都复制到辅助数组assist中

        //4、把辅助数组assist中的元素复制到数组a中
        for(int index=low;index<=high;index++){
            array[index]=assist[index];
        }

        System.out.println(Arrays.toString(array));

        System.out.println("---------------------------------------------------");

    }

}
